package cc.wsyw126.java.nowcoder.sword_offer;

import cc.wsyw126.java.lintCode.swap_two_nodes_in_linked_list.ListNode;

import java.util.HashMap;

/**
 * Created by Administrator on 2017/4/18.
 * 在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。
 * 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5
 */
public class DeleteDuplication {
    public ListNode deleteDuplication(ListNode pHead) {
        HashMap<Integer, Integer> listNodeIntegerHashMap = new HashMap<>();
        ListNode temp = pHead;
        while (temp!= null) {
            Integer integer = listNodeIntegerHashMap.get(temp.val);
            if (integer == null) {
                integer = 0;
            }
            integer++;
            listNodeIntegerHashMap.put(temp.val, integer);
            temp=temp.next;
        }
        temp=pHead;
        ListNode node = new ListNode(0);
        ListNode root = node;
        while (temp!=null) {
            Integer integer = listNodeIntegerHashMap.get(temp.val);
            if (integer == 1) {
                node.next=temp;
                node=temp;
            }
            temp = temp.next;
        }
        node.next=null;
        return root.next;
    }

    public static void main(String[] args) {
        DeleteDuplication deleteDuplication = new DeleteDuplication();
        ListNode listNode = new ListNode(0);
        ListNode listNode1 = new ListNode(1);
        ListNode listNode2 = new ListNode(2);
        ListNode listNode21 = new ListNode(2);
        ListNode listNode3 = new ListNode(3);
        ListNode listNode31 = new ListNode(3);
        ListNode listNode4 = new ListNode(4);
        listNode.next=listNode1;
        listNode1.next=listNode2;
        listNode2.next=listNode21;
        listNode21.next=listNode3;
        listNode3.next=listNode31;
        listNode31.next=listNode4;
        ListNode listNode5 = deleteDuplication.deleteDuplication(listNode);
        while (listNode5 != null) {
            System.out.println(listNode5.val);
            listNode5=listNode5.next;
        }
    }
}
